/**
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 */

#include<string>
#include<hash_set>
#include<vector>
using namespace std;

/**
 * TIPS:滑动窗口
 * s1的排列是s2的子串等价于 s1每个字符的出现次数与s2某个子串的每个字符出现次数相同
 * 次数可以用hashmap统计比较，也可以用26维的数组代替，每个索引对应一个字母
 */
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int len1 = s1.size(), len2 = s2.size();

        if(len1 > len2){
            // s1要是s2的子串
            return false;
        }

        vector<int> count1(26), count2(26);

        // 用vector代替hash，利用字符ASCII相减，26个字母-'a'就能将字母对应到0~25的索引
        for(int i=0; i<len1; i++){
            ++count1[s1[i] - 'a'];
            // 初始化滑动窗口，获得第一个滑动窗口的目标值
            ++count2[s2[i] - 'a'];
            // 判断两个vector相等，因为vector已经实现了operator==这个函数,也就是说它已经重载了==这个操作.
            // 所以,如果vector是内置类型的数据,如int, char等,直接用v1 == v2来判断就可以了,但是如果你用了自定义类型的话,那么首先,你要实现该类型的operator==函数,也就是重载等于判断.
        }
        
        if(count1 == count2){
            return true;
        }
        
        for(int j=len1; j<len2; j++){
            // 继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素
            ++count2[s2[j] - 'a'];
            --count2[s2[j-len1] - 'a'];
            if(count1 == count2){
                return true;
            }
        }

        // 这段是错的，因为单纯的++count2[s2[k]-'a']求的是滑动窗口累计出现的字符个数，不是每个窗口的字符个数
        // for(int j=0; j<len2-len1; j++){
        //     for(int k=j; k<j+len1; k++){
        //         ++count2[s2[k] - 'a'];
        //     }
        //     if(count1 == count2){
        //         return true;
        //     }
        // }
        return false;
    }
};